package algorithmlearn.sort;

import java.util.LinkedList;

//graph traversal  图遍历 path search algorithm
//1.AStar  实现最短路径搜索
//
//A* 算法属于一种启发式搜索算法（Heuristically Search Algorithm）。实际上，启发式搜索算法并不仅仅只有 A* 算法，还有很多其他算法，比如 IDA* 算法、蚁群算法、遗传算法、模拟退火算法等
public class AStarSearchAlgorithm {

    private class Graph {
        Vertex[] vertexes;
        int v;
        LinkedList<Edge>[] adj;

        public Graph(int v) {
            this.vertexes = new Vertex[this.v];
            this.v = v;
            adj = new LinkedList[v];
            for (int i = 0; i < v; i++) {
                adj[i] = new LinkedList<>();
            }
        }

        // Graph 类的成员变量，在构造函数中初始化


        // 新增一个方法，添加顶点的坐标
        public void addVetex(int id, int x, int y) {
            vertexes[id] = new Vertex(id, x, y);
        }

        public void addEdg(int s, int t, int w) {
            adj[s].add(new Edge(s, t, w));
        }

        private class Edge {
            public int sid; // 边的起始顶点编号
            public int tid; // 边的终止顶点编号
            public int w; // 权重

            public Edge(int sid, int tid, int w) {
                this.sid = sid;
                this.tid = tid;
                this.w = w;
            }
        }

        public void astar(int s, int t) { // 从顶点 s 到顶点 t 的路径
            int[] predecessor = new int[this.v]; // 用来还原路径
            // 按照 vertex 的 f 值构建的小顶堆，而不是按照 dist,dijkstra算法只用dist大小构建
            PriorityQueue queue = new PriorityQueue(this.v);
            boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
            vertexes[s].dist = 0;
            vertexes[s].f = 0;
            queue.add(vertexes[s]);
            inqueue[s] = true;
            while (!queue.isEmpty()) {
                Vertex minVertex = queue.poll(); // 取堆顶元素并删除
                for (int i = 0; i < adj[minVertex.id].size(); ++i) {
                    Edge e = adj[minVertex.id].get(i); // 取出一条 minVetex 相连的边
                    Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex

                    if (nextVertex.id == t) { // 只要到达 t 就可以结束 while 了
                        queue.clear(); // 清空 queue，才能推出 while 循环
                        break;
                    }

                    if (minVertex.dist + e.w < nextVertex.dist) { // 更新 next 的 dist,f
                        nextVertex.dist = minVertex.dist + e.w;
                        nextVertex.f
                                = nextVertex.dist + hManhattan(nextVertex, vertexes[t]);
                        predecessor[nextVertex.id] = minVertex.id;
                        if (inqueue[nextVertex.id] == true) {
                            queue.update(nextVertex);
                        } else {
                            queue.add(nextVertex);
                            inqueue[nextVertex.id] = true;
                        }
                    }
                }
            }

            // 输出路径
            System.out.print(s);
            print(s, t, predecessor); // print 函数请参看 Dijkstra 算法的实现
        }

        //曼哈顿距离（Manhattan distance）。曼哈顿距离是两点之间横纵坐标的距离之和。计算的过程只涉及加减法、符号位反转，所以比欧几里得距离(亮点之间的直线距离)更加高效。
        int hManhattan(Vertex v1, Vertex v2) { // Vertex 表示顶点，后面有定义
            return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
        }

        private void print(int s, int t, int[] predecessor) {
            if (s == t) return;
            print(s, predecessor[t], predecessor);
            System.out.print("->" + t);
        }
    }

    // 下面这个类是为了 a* 实现用的
    private class Vertex {
        public int id; // 顶点编号 ID
        public int dist; // 从起始顶点，到这个顶点的距离，也就是 g(i)
        //新增：估价函数 f(i)=g(i)+h(i) ,避免路径查找时“跑偏”
        // 1.这里f(i) 为估价函数（evaluation function）2. h(i) 为曼哈顿距离
        public int f; //
        public int x, y; // 新增：顶点在地图中的坐标（x, y）

        public Vertex(int id, int x, int y) {
            this.id = id;
            this.x = x;
            this.y = y;
            this.f = Integer.MAX_VALUE;
            this.dist = Integer.MAX_VALUE;
        }
    }



    //实现优先级队列，利用堆，小顶堆，利用Vertex的f 大小构建，注意与dijkstra算法的区别，dijkstra只用dist大小构建
    private class PriorityQueue {
        private Vertex[] nodes;
        private int size;

        public PriorityQueue(int v) {
            this.nodes = new Vertex[v + 1];
            this.size = v;
        }

        public void clear(){
            if(size == 0){
                return;
            }
            size = 0;
            for (int i = 0; i < nodes.length; i++) {
                nodes[i] = null;
            }
        }

        public Vertex poll() {
            if (size == 0)
                return null;
            int s = --size;
            Vertex result = nodes[0];
            Vertex x = nodes[s];
            nodes[s] = null;
            if (s != 0)
                siftDown(0, x);
            return result;
        }

        public boolean add(Vertex x) {
            if (x == null)
                throw new NullPointerException();
            int i = size;

            if (i == 0)
                nodes[0] = x;
            else
                siftUp(i, x);
            return true;
        }

        // 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度 O(logn)。
        public boolean update(Vertex x) {
            int i = indexOf(x);
            if (i == -1)
                return false;
            else {
                updateAt(i, x);
                return true;
            }
        }

        private int indexOf(Vertex x) {
            if (x != null) {
                for (int i = 0; i < size; i++)
                    if (x.id == nodes[i].id)
                        return i;
            }
            return -1;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        private Vertex updateAt(int i, Vertex x) {
            int s = --size;
            if (s == i) // updated last element
                siftUp(i, x);
            else {
                siftDown(i, x);
                if (nodes[i] == x) {
                    siftUp(i, x);
                    if (nodes[i] != x)
                        return x;
                }
            }
            return null;
        }

        /**
         * Inserts item x at position k, maintaining heap invariant by
         * promoting x up the tree until it is greater than or equal to
         * its parent, or is the root.
         * <p>
         * To simplify and speed up coercions and comparisons. the
         * Comparable and Comparator versions are separated into different
         * methods that are otherwise identical. (Similarly for siftDown.)
         *
         * @param k the position to fill
         * @param x the item to insert
         */
        private void siftUp(int k, Vertex x) {
            while (k > 0) {
                int parent = (k - 1) >>> 1;
                Vertex e = nodes[parent];
                if (x.f - e.f >= 0)
                    break;
                nodes[k] = e;
                k = parent;
            }
            nodes[k] = x;
        }

        /**
         * Inserts item x at position k, maintaining heap invariant by
         * demoting x down the tree repeatedly until it is less than or
         * equal to its children or is a leaf.
         *
         * @param k the position to fill
         * @param x the item to insert
         */
        private void siftDown(int k, Vertex x) {
            int half = size >>> 1;        // loop while a non-leaf
            while (k < half) {
                int child = (k << 1) + 1; // assume left child is least
                Vertex c = nodes[child];
                int right = child + 1;
                if (right < size &&
                        c.f - nodes[right].f > 0)
                    c = nodes[child = right];
                if (x.f - c.f <= 0)
                    break;
                nodes[k] = c;
                k = child;
            }
            nodes[k] = x;
        }
    }
}
